\section{Solution pour le problème d'optimalité de la coloration}
\label{solution_opti_coloration}

Les problèmes d'optimisation sont souvent résolus à l'aide d'algorithmes par séparation et évaluation, plus connus sous le nom anglais \textsl{branch and bound}~\cite{BBAlgo}. Il s'agit d'une méthode qui, partant du problème initial et son ensemble de solutions possibles, va chercher à énumérer toutes les solutions possibles, par étape, et, à chaque étape, va regarder quelles solutions partielles valent la peine d'être développées. Chaque étape d'un algorithme de séparation et d'évaluation crée, en fixant une des valeurs de l'équation, des sous-problèmes qui auront leur propre ensemble de solutions possibles. Rappelons qu'une solution est possible si elle résout le problème de base et elle est faisable si, en plus, elle respecte les contraintes du problème. La recherche des solutions partielles a une structure d'arbre de recherche (ou de décision), comme représenté en figure~\ref{figBBTree}. \\

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.5]{Images/figBBTree.pdf}
		\caption{Un arbre de recherche (ou de décision)}
		\label{figBBTree}
	\end{center}
\end{figure}

\bigskip
Comme le nom l'indique, les algorithmes de type séparation et évaluation contiennent deux phases. La première, la phase de séparation, est la phase durant laquelle les solutions partielles sont calculées. Partant du problème initial, la séparation crée des sous-problèmes en fixant des valeurs pour l'équation de départ. Il y a donc autant de sous-problèmes que de combinaisons de valeurs possibles. La seconde phase, celle d'évaluation, est la phase durant laquelle les solutions sont gardées ou rejetées. Pour chaque sous-problème, l'évaluation va calculer la meilleure solution possible qu'on peut obtenir avec ce début de solution construit. Cette solution ne doit pas forcément respecter les contraintes du problème et sera donc une borne inférieure qui permettra de savoir si une solution partielle en construction vaut la peine d'être développée ou non. Lorsque cette solution est faisable (elle respecte donc les contraintes), l'algorithme retiendra la valeur du coût de cette solution, qu'on appelle \textsl{incumbent}. C'est cette valeur qui servira de repère pour savoir si une solution partielle en construction vaut la peine ou non: si sa borne est moins bonne que l'\textsl{incumbent} actuel, la solution ne sera pas développée. À la fin de la recherche, c'est-à-dire au niveau des feuilles de l'arbre, le plus petit \textsl{incumbent} (ou l'un des plus petits, s'il y en a plusieurs) est donc la solution finale de notre problème (dans le cas d'une minimisation, toujours). Illustrons la technique de séparation et d'évaluation par un exemple. \\

Imaginons que notre problème soit une assignation de tâches à des personnes telle que chaque personne effectue une et une seule tâche et que toutes les tâches doivent avoir une personne assignée et que la durée d'exécution de toutes les tâches soit minimale. Soient quatre personnes, A, B, C et D et quatre tâches $1$, $2$, $3$ et $4$. La table ci-dessous représente le nombre de minutes nécessaires aux personnes pour effectuer chaque tâche. \\
\begin{center}
	\begin{tabular}{|c|c|c|c|c|}
		\hline
		 & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} \\
		\hline
		\textbf{A} & 10 & 4 & 12 & 7 \\
		\hline
		\textbf{B} & 5 & 8 & 21 & 4 \\
		\hline
		\textbf{C} & 9 & 5 & 11 & 9 \\
		\hline
		\textbf{D} & 7 & 6 & 8 & 3 \\
		\hline
	\end{tabular}
\end{center}

\bigskip
Le point de départ de l'algorithme, le problème initial, n'a pas encore de valeur fixée (c'est-à-dire qu'il n'y a aucune tâche assignée) et on calcule une borne en créant une solution qui assigne les tâches aux personnes qui les exécutent le plus rapidement (on relâche la contrainte d'une personne par tâche), ce qui nous donne comme solution: BADD avec une valeur de borne de $5 + 4 + 8 + 3 = 20$. Ensuite, on va créer les sous-problèmes de ce problème initial en assignant la première tâche à une personne. \\

Il y a quatre sous-problèmes possibles: on peut assigner la première tâche à la personne A, B, C ou D. Dans les schémas qui suivront, les personnes auxquelles une tâche est fixée seront notées en gras. Pour chacun de ces sous-problèmes, on calcule une borne en assignant, de la meilleure façon possible, les trois dernières tâches aux trois autres personnes (respect de la contrainte d'une tâche par personne). À la fin de cette étape et du calcul des bornes, on obtient l'arbre de recherche représenté en partie gauche de la figure~\ref{figBBEx01}. Remarquez que la solution \textbf{D}ACB respecte (par chance) la contrainte d'une tâche par personne et est une solution faisable, ce qui signifie que l'\textsl{incumbent} reçoit la valeur de cette borne, soit $26$. Grâce à cet \textsl{incumbent}, on peut retirer la solution \textbf{A}CDD de notre recherche puisque sa borne n'est pas meilleure. \\

On passe à l'étape suivante en développant la solution la plus prometteuse, celle avec la plus petite borne, soit \textbf{B}ADD. Des trois sous-problèmes de ce n\oe{}ud, on peut éliminer \textbf{BD}CA puisque sa borne n'est pas meilleure que l'\textsl{incumbent}. Après avoir généré les sous-problèmes de \textbf{B}ADD, on fait de même pour \textbf{C}ADD et \textbf{D}ACB. La partie droite de la figure~\ref{figBBEx01} représente la fin de cette seconde étape. Deux des trois sous-problèmes de \textbf{C}ADD peuvent être éliminés, de même que deux des trois sous-problèmes de \textbf{D}ACB, ce qui ne laisse que quatre n\oe{}uds à développer sur les douze potentiels de cette étape (trois possibilités pour la tâche 2 pour chacune des possibilités pour la tâche 1, au nombre de 4: $4*3 = 12$). Il n'y a pas de meilleure solution faisable à cette étape, donc l'\textsl{incumbent} ne change pas. \\

\begin{comment}
\begin{figure}[ht]
	\begin{minipage}[b]{0.5\linewidth}
		\begin{center}
			\includegraphics[scale=0.4]{Images/figBBEx01.pdf}
			\caption{L'arbre de recherche après la première étape}
			\label{figBBEx01}
		\end{center}
	\end{minipage}
	\hspace{0.5cm}
	\begin{minipage}[b]{0.5\linewidth}
		\begin{center}
			\includegraphics[scale=0.4]{Images/figBBEx02.pdf}
			\caption{L'arbre de recherche après la deuxième étape}
			\label{figBBEx02}
		\end{center}
	\end{minipage}
\end{figure}
\end{comment}

\begin{figure}[h!]
	\centerline{
		\mbox{\includegraphics[scale=0.5]{Images/figBBEx01.pdf}}
		\mbox{\includegraphics[scale=0.5]{Images/figBBEx02.pdf}}
  	}
  	\caption{L'arbre de recherche après la première (à gauche) et la deuxième (à droite) étape}
	\label{figBBEx01}
\end{figure}

\bigskip
Pour la troisième étape, on commence par développer le n\oe{}ud le plus prometteur, c'est-à-dire \textbf{BA}DD. Il existe deux possibilités de sous-problème pour ce n\oe{}ud, \textbf{BAC}D et \textbf{BAD}C. Les deux sont, évidemment, des solutions faisables et \textbf{BAC}D possède la meilleure valeur, $23$, donc l'\textsl{incumbent} prendra cette valeur. De là, on peut s'apercevoir que \textbf{BAD}C n'est pas une meilleure solution et que les deux n\oe{}uds \textbf{CA}DD et \textbf{DA}CB ne valent pas la peine d'être développés. Il ne reste donc plus que le n\oe{}ud \textbf{BC}DD à développer. Les deux sous-problèmes générés ne sont pas meilleurs que l'\textsl{incumbent} actuel et ne sont donc pas considérés comme solutions. L'arbre de recherche final se trouve en figure~\ref{figBBEx03}. \\

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.5]{Images/figBBEx03.pdf}
		\caption{L'arbre de recherche à la fin}
		\label{figBBEx03}
	\end{center}
\end{figure}

\bigskip
En conclusion, il a fallu 3 étapes et 17 calculs de solution pour arriver à la solution finale: BACD qui signifie qu'on assigne la tâche 1 à la personne B, la tâche 2 à la personne A, la tâche 3 à la personne C et la tâche 4 à la personne D. Il n'y a eu donc que 17 calculs au lieu de $4! = 24$ ce qui fait 30\% des recherches évitées. Bien sûr, sur un problème plus conséquent, comme celui que nous traitons dans ce mémoire, le ratio de recherches éliminées est généralement bien plus important. \\

La principale difficulté, lorsqu'il faut concevoir un algorithme de ce type, est d'avoir une bonne fonction d'évaluation, c'est-à-dire une fonction qui permettra d'avoir une bonne borne. En effet, plus la fonction calcule une bonne borne, plus il y aura d'éliminations de solutions partielles et plus rapide sera l'algorithme. Pour avoir une bonne fonction d'évaluation, on relâche une contrainte afin d'obtenir une borne optimiste. Dans le cas de notre problème de coloration, dont la formule de minimisation et les contraintes sont: 

\begin{equation}
	\label{equation_min_2_}
	min (\alpha \sum_{n \in V: c_n \neq blanc} (1 - X_{k(n)_{c_n}}) + \beta \sum_{e = (a, b, p_e) \in E} p_e Y_e)
\end{equation}
\begin{align*}
	\text{Sous les contraintes}
	\begin{cases}
		\sum_{c \in C} X_{k_c} = 1 \; (1 \leq k \leq K) \\
		Y_e \geq X_{k(i)_c} - X_{k(j)_c} \; (\forall e = (i,j) \in E, c \in C) \\
		X_{k(a)_{c_i}} = 1 \; (\forall a \in d_i, 1 \leq i \leq m)
	\end{cases}
\end{align*}

\noindent
il serait possible de relâcher la dernière contrainte qui impose une couleur à certains n\oe{}uds. De cette manière, soit aucun n\oe{}ud n'a de contraintes de couleur et les solutions recherchées sont des solutions faisables, soit certains n\oe{}uds ont des contraintes de couleur et les solutions recherchées seront meilleures que les solutions faisables (pour lesquelles les contraintes de couleurs devront être respectées). Si le coût $C_t$, en retirant cette dernière contrainte, est un minimum, l'équation d'optimisation sera également un minimum. Les propriétés d'une fonction d'évaluation, 
\begin{align*}
	& g(P_i) \leq f(P_i) \; \text{ pour chaque n\oe{}ud } P_i \text{ dans l'arbre de recherche}, \\
	& g(P_i) \leq f(P_i) \; \text{ pour chaque feuille } P_i \text{ dans l'arbre de recherche}, \\
	& g(P_i) \geq g(P_j) \; \text{ si } P_j \text{ est un parent de } P_i,
\end{align*}
sont respectées. Décrivons ces propriétés et montrons qu'elles sont respectées dans notre cas: 
\begin{description}
	\item[Propriété n°1:] Pour chaque n\oe{}ud de l'arbre de recherche, il faut que la borne calculée soit inférieure ou égale à la valeur réelle de la solution (sans relâchement de contraintes). C'est effectivement le cas, comme nous l'avons décrit ci-dessus.
	\item[Propriété n°2:] Pour chaque feuille, la valeur de la borne est égale à la valeur réelle de la solution. En effet, lorsqu'on développe une solution en construisant les fils de cette solution, il faut respecter toutes les contraintes. Dès lors, dans les feuilles de l'arbre de recherche, une couleur a été assignée à chacun des n\oe{}uds de l'arbre et la valeur de cette solution est la même que la valeur de la borne puisque la contrainte relâchée pour le calcul de la borne ne l'a pas été pour la construction de cette solution finale. 
	\item[Propriété n°3:] Pour chaque feuille, la valeur de la borne est supérieure ou égale à la valeur de la borne de son père. En effet, en construisant un fils $i$ d'un n\oe{}ud $j$, on a respecté la contrainte relâchée pour le calcul de la borne, ce qui signifie que, potentiellement, un n\oe{}ud a dû changer de couleur par rapport à la solution de $j$ où la contrainte sur ce n\oe{}ud n'était pas appliquée.
\end{description}

\bigskip
Dans~\cite{BBAlgo}, un algorithme de séparation et d'évaluation est donné et montré, ici, dans l'algorithme~\ref{BBAlgo}. Dans cet algorithme, \texttt{Live} est l'ensemble des n\oe{}uds en vie, c'est-à-dire qu'il reste encore à traiter. Cet ensemble sera tout d'abord initialisé par le premier n\oe{}ud de l'arbre, la racine, qui correspond au problème initial. Par la suite, lorsqu'une solution générée aura une meilleure borne que l'\textsl{l'incumbent}, cette solution sera ajoutée à l'ensemble \texttt{Live}. \texttt{LB} est la borne calculée d'un n\oe{}ud $P_i$, via la fonction d'évaluation $g()$. Enfin, il est facile de s'apercevoir que, lorsque l'ensemble \texttt{Live} sera vide, c'est-à-dire que l'algorithme aura traité toutes les solutions, la dernière solution gardée sera la solution optimale et le dernier \textsl{incumbent} gardé sera la valeur optimale de la solution. \\

\begin{algorithm}
	\caption{Détermine la solution optimale par la technique du \textsl{Branch and Bound}}
	\label{BBAlgo}
	\begin{algorithmic}
		\STATE $Incumbent \leftarrow \infty$
		\STATE $LB(P_0) \leftarrow g(P_0)$
		\STATE $Live \leftarrow \lbrace (P_0, LB(P_0)) \rbrace$
		\WHILE{$Live = \emptyset$}
			\STATE Sélectionner le n\oe{}ud $P$ dans $Live$ à être traité
			\STATE $Live \leftarrow Live \setminus \lbrace P \rbrace$
			\STATE Générer les solutions partielles $P_1$, $P_2$, ..., $P_3$ à partir de $P$
			\FOR{$i = 1$ \TO $k$}
				\STATE $LB(P_i) \leftarrow g(P_i)$
				\IF {$LB(P_i) = f(X)$ pour une solution faisable $X$ et $f(X) < Incumbent$}
					\STATE $Incumbent \leftarrow f(X)$
					\STATE $Solution \leftarrow X$
				\ELSIF {$LB(P_i) \geq Incumbent$}
					\STATE Élimination de $P_i$
				\ELSE
					\STATE $Live \leftarrow Live \cup \lbrace (P_i, LB(P_i)) \rbrace$
				\ENDIF
			\ENDFOR
		\ENDWHILE
	\end{algorithmic}
\end{algorithm}

Nous avons donc une technique pour trouver le minimum de l'équation~\ref{equation_min_2_}, ce qui nous permet de trouver une coloration qui respecte les contraintes et qui fait le bon nombre de modifications de couleur pour obtenir un coût de changement minimal. Dans la prochaine section, nous verrons comment les solutions proposées pour le problème de comparaison et le problème de coloration peuvent être remises dans le contexte de départ: la redistribution de code \textsl{dSL}.